iT邦幫忙

2023 iThome 鐵人賽

DAY 21
0

雙向佇列(Double-Ended Queue)

雙向佇列是一般話的佇列或堆疊。跟佇列的「先進先出FIFO」,和堆疊「後進後出LIFO」比起,雙向佇列可以從最前端或最尾端任意方向,在常數時間複雜度內增刪元素,更為方便。

基本操作

雙向佇列有符合定義的基本操作:

🚀 new:初始化一個容器。

🚀 push_front: 在容器最前端新增一個元素。

🚀 push_back: 在容器最尾端新增一個元素。

🚀 pop_front: 移除在容器最前端的元素。

🚀 pop_back: 移除在容器最尾端的元素。

為了提升方便性,也提供一些方法:

🛸 front: 查看容器最前端的元素。

🛸 back: 查看容器最尾端的元素。

🛸 len: 檢查容器內的元素數目。

🛸 is_empty: 檢查容器是否沒有任何元素。

🛸 iter、iter_mut、into_iter: 產生一個疊代容器內所有元素的疊代器。

需要精準控制記憶體,提供內部方法:

🛰 is_full: 檢查底層環形緩衝區是否滿載。

🛰 try_grow: 嘗試動態增加底層儲存空間。

🛰 wrapping_add、wrapping_sub: 確保邏輯索引的增減正確映射到底層實際索引位址。

雙向佇列就是允許兩端中的任意具備刪除或加入,無論左右兩端的佇列,前端跟尾端都是朝佇列中央來移動。一班的應用,雙向佇列分為資料從一端加入,但可從兩端取出,另一種是可由兩端加入,但由一端取出。

struct Deque {
    head: usize,
    tail: usize,
    storage: SomeStorageType,
}

範例:

以鏈結串列來設計雙向佇列,從任意端輸入但從後端取出:

struct RestrictedDeque<T> {
    list: LinkedList<T>,
}

impl<T> RestrictedDeque<T> {
    fn new() -> Self {
        RestrictedDeque {
            list: LinkedList::new(),
        }
    }

    // 從(前端)加入
    fn push(&mut self, data: T) {
        self.list.push_front(data);
    }

    // 從前端取出
    fn pop_front(&mut self) -> Option<T> {
        self.list.pop_front()
    }

    // 從後端取出数
    fn pop_back(&mut self) -> Option<T> {
        self.list.pop_back()
    }
}

優先佇列(Priority Queue)

優先佇列不必遵守佇列特性-**FIFO(先進先出)**的有序串列,其中每一個元素都賦予優先權,加入元素時可任意輸出,但有最高優先權者則最先輸出。

假設有4個行程A1,A2,A3,A4,在短時間先後到達等待佇列,每個行程執行時間如:

行程名稱 所需時間
A1 50
A2 10
A3 25
A4 15

這邊給4個行程優先權A1:1,A2:2,A3:3,A4:4(假設數值越小其優先權越低)。

範例:

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn main() {
    // 建立一個空的佇列
    let mut priority_queue: BinaryHeap<Reverse<i32>> = BinaryHeap::new();

    // 新增元素到佇列
    priority_queue.push(Reverse(5));
    priority_queue.push(Reverse(2));
    priority_queue.push(Reverse(7));
    priority_queue.push(Reverse(1));

    // 從優先陣列中彈出元素,按照優先排序
    while let Some(Reverse(value)) = priority_queue.pop() {
        println!("彈出: {}", value);
    }
}

這範例用Rust的'BinaryHeap'來實現,BinaryHeap默許最大值在前,輸出結果在用Reverse來做包裝。

堆疊和佇列的實作大概會講到這邊,主要遵守先進先出和後進後出的原理就能理解,但還是要實際做過類似的問題才會比較知道運作。

目前應該不會太難吧🍹🍹!!

要是哪裡理解上還是邏輯上有錯請各位大大指正,感謝 🧙🧙🧙。

資料來源:

https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html

https://doc.rust-lang.org/std/cmp/struct.Reverse.html


上一篇
「Day20」陣列&鏈結串列實作佇列
下一篇
「Day22」樹狀演算法
系列文
Easy to learn Algorithm30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言